import collections
import heapq
import functools
class Solution(object):
    def countRestrictedPaths(self, n, edges):
        d = collections.defaultdict(dict)
        for u, v, dist in edges:
            d[u][v] = dist
            d[v][u] = dist
        distance = [-1] * (n + 1)
        distance[-1] = 0
        st = []
        for v in d[n]:
            st.append([d[n][v], v])
        heapq.heapify(st)
        while st:
            while st and distance[st[0][1]] >= 0:
                heapq.heappop(st)
            if st:
                dist, u = heapq.heappop(st)
                distance[u] = dist
                for v in d[u]:
                    heapq.heappush(st, [dist + d[u][v], v])

        @functools.cache
        def dfs(i):
            if i == n:
                return 1
            else:
                ans = 0
                for j in d[i]:
                    if distance[j] < distance[i]:
                        ans += dfs(j)
                return ans

        return dfs(1) % (10 ** 9 + 7)